算法分析

关于学习
算法分析
- 插入排序
  - 伪代码
  - 分析

关于学习

如果学习过程中遇到难题, 可以自己独立地认真思考半小时左右, 如果半小时后仍然没有什么进展, 那么把时间都浪费在难题上是没有意义的. 可以选择与其他人交流, 合作解决问题.

算法分析

首先要分析程序的性能(主要是它的运行速度)和运行该程序所耗费的资源, 如内存空间, 磁盘空间等.

性能很重要, 性能的好坏, 决定着程序是否可行. 比如, 在实时性要求严格的应用场景下, 如果性能较差, 直接导致程序不可行.

在实际应用中, 也许除了性能, 我们会更加关注程序的安全性, 用户体验, 模块化等. 但为什么还要学习算法分析以改善性能? 教授作了一个很好的比喻, 对人来说, 钱很重要, 但是食物更加重要, 那为什么还需要钱? 因为钱是基础, 人们用钱来获得其他需要的东西, 这也同样适用于性能所处的层次, 即相对安全, 用户体验等来说较为底层.

插入排序

我们通过插入排序, 来看一下如何进行算法分析.

伪代码

Insertion-Sort(A, n)  // Sorts A[1...n]
	for j <- 2 to n
		do key <- A[j]
			i <- j-1
			while i>0 and A[i]>key
				do A[i+1] <- A[i]
					i <- i-1
			A[i+1] = key

分析

每次需要排序的数, 备份到 key. A[0...j-1] 表示排好序的数, A[j...n] 表示未排序的数. 0 <= i <= j-1.

如果 key 要插入到 A[i] 的后面, 则 [i+1, j-1] 之间的数, 全部往后移动一位, 这样, 原本的 A[i+1], 就成了 A[i+2], 然后令 A[i+1]=key. 如:

Pinvon's Blog

算法分析

Table of Contents

关于学习

算法分析

插入排序

伪代码

分析

Comments